package leetcode_1801_1900;

import java.util.Arrays;
import java.util.TreeSet;

public class LeeCode_1818 {
    public static void main(String[] args) {

    }
    private static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        long sum = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(nums1[i]);
            sum += Math.abs(nums1[i] - nums2[i]);
        }
        int diff = 0;
        for (int i = 0; i < nums2.length; i++) {
            int c1 = Integer.MAX_VALUE, c2 = Integer.MAX_VALUE, x = nums2[i];
            Integer higher = set.higher(x - 1);
            Integer lower = set.lower(x + 1);
            if (higher != null)
                c1 = Math.abs(x - higher);
            if (lower != null)
                c2 = Math.abs(x - lower);
            int min = Math.min(c1, c2);
            diff = Math.max(diff, Math.abs(nums2[i] - nums1[i]) - min);
        }
        return (int) ((sum - diff) % (1e9 + 7));
    }
}